class Solution {
public:
    vector<int> rearrangeBarcodes(vector<int>& b) {
        int n=b.size();
        unordered_map<int,int> hash;
        for(int i=0;i<n;++i)
        {
            hash[b[i]]++;
        }
        vector<int> ret(n,0);
        auto cmp=[&](int a,int b){
            return hash[a]<hash[b];
        };
        priority_queue<int,vector<int>,decltype(cmp)> q(cmp);
        for(auto x:hash)
        {
            q.push(x.first);
        }
        int index=0;
        while(q.size())
        {
            int nums=q.top();
            q.pop();
            int count=hash[nums];
            while(count-->0)
            {
                if(index>=n)
                    index=1;
                ret[index]=nums;
                index+=2;
            }
        }
        return ret;
    }
};
